﻿#define _CRT_SECURE_NO_WARNINGS 
//const int N = 1e6 + 10;
//int heap[N];
//int n;
//// 向上调整算法
//void up(int child)
//{
//    int parent = child / 2;
//    while (parent >= 1 && heap[child] < heap[parent])
//    {
//        swap(heap[child], heap[parent]);
//        child = parent;
//        parent = child / 2;
//    }
//
//}
//
//void down(int parent)
//{
//    int child = parent * 2;
//    while (child <= n)
//    {
//        if (child + 1 <= n && heap[child + 1] < heap[child])child++;
//        if (heap[child] >= heap[parent])return;
//        swap(heap[child], heap[parent]);
//        parent = child;
//        child = parent * 2;
//    }
//}
//
//void push(int x)
//{
//    n++;
//    heap[n] = x;
//    up(n);
//}
//
//void pop()
//{
//    swap(heap[1], heap[n]);
//    n--;
//    down(1);
//}
//
//int main()
//{             
//    int t; cin >> t;
//    int  op;
//    int x;
//    while (t--)
//    {
//        cin >> op;
//        switch (op)
//        {
//        case 1:
//            cin >> x;
//            push(x);
//            break;
//        case 2:
//            cout << heap[1] << endl;
//            break;
//        case 3:
//            pop();
//            break;
//        default:
//            break;
//        }
//    }             
//   return 0;
//}



#include<algorithm>
#include<queue>
#include<vector>
#include<iostream>
using namespace std;

//#include<iostream>
//using namespace std;
//
//priority_queue<int>heap;
//int main()
//{
//	int n, m, k;
//	int op;
//	int x;
//	cin >> n >> m >> k;
//
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> x; heap.push(x);
//		if (heap.size() > k)heap.pop();
//	}
//
//	while (m--)
//	{
//		cin >> op;
//		if (op == 1)
//		{
//			cin >> x;
//			heap.push(x); 
//			if (heap.size() > k) heap.pop();
//		}
//		if (op == 2)
//		{
//			if (heap.size() == k)cout << heap.top() << endl;
//			else cout << -1 << endl;
//		}
//	}
//	return 0;
//}
//const int N = 3e5 + 100;
//int num, op, x;
//int n, m, k;
//int a[N];
//int main()
//{
//	cout << "测试" << endl;
//	cin >> n >> m >> k;
//	int num = n;
//	for (int i=0;i<n;i++)
//	{
//		cin >> a[i];
//	}
//	
//	sort(&a[0],&a[n-1]);
//	while (m--)
//	{
//		cin >> op;
//		if (op == 1)
//		{
//			n++;
//			cin >> a[n-1];
//		}
//		
//		if (op == 2)
//		{
//			sort(&a[0], &a[n-1]);
//			cout << a[k] << endl;
//		}
//	}
//	return 0;
//}

  
//#include<queue>
//#include<vector>
//#include<iostream>
//using namespace std;
//int a[10] = { 1,99,78,213,23,56,15,-12,0,18 };
//
//
//struct node
//{
//	int a, b, c;
//	// 重载<运算符
//	// 以b为基准 ，创大根堆
//	bool operator<(const node& x)const
//	{
//		return b < x.b;//创建小根堆只需要改成 b>x.b ;
//	}
//
//};
//// 结构体类型
//void test2()
//{
//	priority_queue<node>heap2;
//	for (int i = 1; i <= 5; i++)
//	{
//		heap2.push({ -i,i + 1,i + 2 });
//	}
//	while (heap2.size())
//	{
//		node t = heap2.top(); 
//		heap2.pop();
//		cout << t.a <<" " << t.b <<" " << t.c << endl;
//	}
//}
//
//// 内置类型
//void test1()
//{
//	priority_queue<int>heap1;// 默认 大根堆
//
////  priority_queue<数据类型, 存储结构, 比较方式>名称;
//	priority_queue<int, vector<int>, less<int>>heap2;// less是小于（大根堆）// greater是大于（小根堆）
//
//}
//int main()
//{   // 优先级队列
//	// 当做堆
//	priority_queue<int>heap;// 默认 大根堆
//	for (int i = 0; i < 10; i++)
//	{
//		heap.push(a[i]);
//	}
//	while (heap.empty())
//	{
//		cout << heap.top() << " ";
//		heap.pop();
//	}
//	test2();
//	return 0;
//}


// //模版题 栈
//int main()
//{
//	priority_queue<int, vector<int>, greater<int>>heap;
//	int n;
//	cin >> n;
//	int op;
//	int x;
//	while (n--)
//	{
//		cin >> op;
//		switch (op)
//		{
//		case 1:
//			cin >> x;
//			heap.push(x);
//			break;
//		case 2:
//			cout << heap.top() << endl;
//			break;
//		case 3:
//			heap.pop();
//			break;
//		default:
//			break;
//		}
//	}
//	return 0;
//}

